package linkList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

import utils.linkListUtil;
import utils.linkListUtil.ListNode;
import utils.linkListUtil.Node;

public class sortList {
    // 大坑，数字可重复,因此map中的元素得用list，要不然会覆盖
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 排序后，head就变了
        ListNode first = head;
        // 空间换时间
        HashMap<Integer, List<ListNode>> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        while (first != null) {

            list.add(first.val);
            List<ListNode> subList = map.getOrDefault(first.val, new ArrayList<>());
            subList.add(first);
            map.put(first.val, subList);

            first = first.next;
        }
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            };
        });
        first = null;
        for (Integer val : list) {
            List<ListNode> node = map.get(val);
            for (ListNode subNode : node) {
                if (first == null) {
                    first = subNode;
                    head = first;
                } else {
                    first.next = subNode;
                    first = subNode;
                }
            }

        }
        // 最后一个元素要执行null，否则可能出现环
        first.next = null;
        return head;
    }

    public static void main(String[] args) {
        int[] l1 = new int[] { 4, 19, 14, 5, -3, 1, 8, 5, 11, 15 };
        ListNode list1 = linkListUtil.createLinkedList(l1);
        ListNode mergeTwoLists = sortList(list1);
        while (mergeTwoLists != null) {
            System.out.println(mergeTwoLists.val);
            mergeTwoLists = mergeTwoLists.next;
        }
    }
}
